package main

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
 *
 * @param head1 ListNode类
 * @param head2 ListNode类
 * @return ListNode类
 */
func addInList(head1 *ListNode, head2 *ListNode) *ListNode {
	// write code here
	head1 = reverse(head1)
	head2 = reverse(head2)
	return reverse(solve(head1, head2, 0))
}

func solve(head1 *ListNode, head2 *ListNode, carry int) *ListNode {
	if head1 == nil && head2 == nil {
		if carry != 0 {
			return &ListNode{Val: carry}
		}
		return nil
	}
	if head1 == nil {
		sum := head2.Val + carry
		head2.Next = solve(head1, head2.Next, sum/10)
		head2.Val = sum % 10
		return head2
	}
	if head2 == nil {
		sum := head1.Val + carry
		head1.Next = solve(head1.Next, head2, sum/10)
		head1.Val = sum % 10
		return head1
	}
	sum := head1.Val + head2.Val + carry
	head1.Next = solve(head1.Next, head2.Next, sum/10)
	head1.Val = sum % 10
	return head1
}

func reverse(head1 *ListNode) *ListNode {
	pre := (*ListNode)(nil)
	current := head1
	for current != nil {
		next := current.Next
		current.Next = pre
		pre = current
		current = next
	}
	return pre
}
